import java.util.PriorityQueue;

public class BM12 {

    public class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode sortInList(ListNode head) {
        // write code here
        // write code here
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        while(head != null){
            pq.add(head);
            head = head.next;
        }
        ListNode nullHead = new ListNode(0);
        ListNode tail = nullHead;
        while(!pq.isEmpty()){
            tail.next = pq.poll();
            tail = tail.next;
            tail.next = null;
        }
        return nullHead.next;
    }
}
